package hyy_2022;

import commons.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 两个二叉树相同,当且仅当两个二叉树的结构完全相同,且所有对应的节点的值相同
 *
 */
public class _0826_100_IsSameTree {

    /**
     * 深度优先搜索
     * @param p
     * @param q
     * @return boolean
     */
    public boolean isSameTreeByDFS(TreeNode p, TreeNode q) {
        if(p == null && q == null) {
            return true;
        } else if(p == null || q == null) {
            return false;
        } else if(p.val != q.val) {
            return false;
        } else {
            return isSameTreeByDFS(p.right,q.left) && isSameTreeByDFS(p.right,q.right);
        }
    }

    /**
     * 广度优先搜索
     * 1、判断两个二叉树是否为空,如果两个二叉树都不为空,则从两个二叉树的根节点开始广度优先搜索
     * 2、使用两个队列分别存储两个二叉树的节点。初始时将两个二叉树的根节点分别插入两个队列,每次从两个队列各取一个节点,进行如下比较操作:
     *          比较两个节点的值,如果两个节点的值不相同则两个二叉树一定不相同
     *          如果两个节点的值相等,则判断两个节点的子节点是否为空,如果只有一个节点的左子节点为空,或只有一个节点的右子节点为空,则两个
     *          二叉树的结构不同,因此两个二叉树一定不同
     *          如果两个节点的子节点结构相同,则将两个节点的非空子节点分别加入两个队列,子节点加入队列的顺序要注意,如果左右子节点都不为空,
     *          则先加入左子节点,后加入右子节点
     * @param p
     * @param q
     * @return boolean
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        }
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
        queue1.offer(p);
        queue2.offer(q);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            if (node1.val != node2.val) {
                return false;
            }
            TreeNode left1 = node1.left, right1 = node1.right, left2 = node2.left, right2 = node2.right;
            if (left1 == null ^ left2 == null) {
                return false;
            }
            if (right1 == null ^ right2 == null) {
                return false;
            }
            if (left1 != null) {
                queue1.offer(left1);
            }
            if (right1 != null) {
                queue1.offer(right1);
            }
            if (left2 != null) {
                queue2.offer(left2);
            }
            if (right2 != null) {
                queue2.offer(right2);
            }
        }
        return queue1.isEmpty() && queue2.isEmpty();
    }


}
